#!/usr/bin/python
# coding: utf-8

import sys
sys.path.append('../dinprog/')
from optparse import Option, OptionParser
from math import log

from sflib.py_finder import create_norm_mx, print_mx
from sflib.py_finder import chi_dist_mx, chi2prob

ALPHABET = 'actg'
PERIOD   = 3

F_MIN = 4.0
F_MAX = 100.0

def find_shifts(opts, (seq_id, seq)):
    N = len(seq)
    
    for win_length in xrange(60, 600, PERIOD):
        for x in xrange(win_length, N-win_length-PERIOD+2):
            mx_left  = create_norm_mx(seq[x-win_length:x])
            mx_rights = [create_norm_mx(seq[x+p:x+p+win_length]) for p in xrange(PERIOD)]
            
            probs = [chi2prob(chi_dist_mx(mx_left, mx_right)) for mx_right in mx_rights]
            p0 = probs[0]
            for i, p in enumerate(probs):
                if p == 0:
                    f = F_MAX
                elif p0 == 0:
                    f = -F_MAX
                else:
                    f = log(p/p0) / log(10.0)
                if f > F_MIN:
                    print '%s\t%s\t%s\t%s\t%s' % (seq_id, x, win_length, i, f)


if __name__ == '__main__':
    parser = OptionParser(usage='%prog [-l WIN_LENGTH]')
    parser.add_option(Option(
        '-l', '--window-length',
        dest = 'win_length',
        type = int,
        default = 36,
    ))
    parser.add_option(Option(
        '-v', '--verbose',
        dest = 'verbose',
        action = 'store_true',
        default = False,
    ))

    options, args = parser.parse_args()
    if options.win_length % PERIOD != 0:
        print >> sys.stderr, "WIN_LENGTH is not divided by %s" % PERIOD
        sys.exit(1)
        
    for line in sys.stdin:
        id, line = line.strip().split()
        find_shifts(options, (id, line))
